<?php
//朴素算法即暴力匹配
function naiveStringSearch($s,$p){
    $i = 0;
    $j = 0;
    $slen = strlen($s);
    $plen = strlen($p);
    $sarr = str_split($s);
    $parr = str_split($p);

    while($i<$slen && $j<$plen){
        if($sarr[$i] == $parr[$j]){
            $i++;
            $j++;
        } else {
            $i = $i-$j +1;//向前移动
            $j = 0;
        }
    }
    if ($j == $plen){
        return $i-$j;
    }
    return -1;
}
//kmp算法之过去next数组,对模式串处理
function getNext1($p) { //未优化版本
    $i = 0 ;
    $j = -1;
    $plen = strlen($p);
    $arr = array("0"=>-1);
    $parr = str_split($p);
    while($i < $plen) {
        if($j == -1 || $parr[$i] == $parr[$j]) {
            $i++;
            $j++;
            $arr[$i] = $j;
        } else {
            $j = $arr[$j];
        }
    }
    return $arr;
}

function getNext2($p) { //未优化版本
    $i = 0 ;
    $j = -1;
    $plen = strlen($p);
    $arr = array("0"=>-1);
    $parr = str_split($p);
    while($i < $plen) {
        if($j == -1 || $parr[$i] == $parr[$j]) {
            $i++;
            $j++;
            if($parr[$i] != $parr[$j])
                $arr[$i] = $j;
            else
                $arr[$i] = $arr[$j];//既然相同就继续往前找真前缀
        } else {
            $j = $arr[$j];
        }
    }
    return $arr;
}

function kmp($s,$p){
    //$arr = getNext1($p);
    $arr = getNext2($p);
    var_dump(json_encode($arr));
    $i = 0;
    $j = 0;
    $s_len = strlen($s);
    $p_len = strlen($p);
    var_dump("s_len:$s,p_len:$p_len");
    $sarr = str_split($s);
    $parr = str_split($p);
    while($i< $s_len && $j < $p_len) { // 因为末尾 '\0' 的存在，所以不会越界
        if($j == -1 || $sarr[$i] == $parr[$j]){
            $i++;
            $j++;
        } else {
            $j = $arr[$j];// 当前字符匹配失败，进行跳转
        }
        echo "$i | ";
    }
    var_dump("$i:$j");
    if($j == $p_len){
        return $i-$j;
    }
    return -1;
}

$s = "bbc abcdab abcdabcdabde";
$p = "abcdabd";

//var_dump(naiveStringSearch($s,$p));
var_dump(kmp($s,$p));